package list

func mergeKLists(lists []*ListNode) *ListNode {
	if len(lists) == 0 {
		return nil
	}

	var helper func(l1 *ListNode, l2 *ListNode) *ListNode
	helper = func(l1 *ListNode, l2 *ListNode) *ListNode {

		dummyHead := &ListNode{
			Val:  -1,
			Next: nil,
		}
		temp := dummyHead
		for l1 != nil && l2 != nil {
			if l1.Val < l2.Val {
				temp.Next = l1
				l1 = l1.Next
			} else {
				temp.Next = l2
				l2 = l2.Next
			}
			temp = temp.Next
		}

		if l1 == nil {
			temp.Next = l2
		} else {
			temp.Next = l1
		}

		return dummyHead.Next

	}

	for len(lists) >= 2 {
		list1 := lists[len(lists)-1]
		list2 := lists[len(lists)-2]
		lists = lists[:len(lists)-2]
		lists = append(lists, helper(list1, list2))
	}

	return lists[0]
}
